package com.sicheng.lc.杂题.多路归并技巧之构造有序链表;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/12 15:47
 */
public class 超级丑数 {
    //https://leetcode.cn/problems/super-ugly-number/

    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        PriorityQueue<int[]> heap = new PriorityQueue<>(primes.length,
                Comparator.comparingLong(a -> (long) dp[a[1]] * primes[a[0]]));
        for (int i = 0; i < primes.length; i++) {
            heap.offer(new int[]{i, 1});
        }
        for (int i = 2; i <= n; i++) {
            if (heap.isEmpty())
                break;
            int[] a = heap.poll();
            // 当前节点和上一个dp[i]重复就指针下滑 塞回去 再拉出来
            while (dp[a[1]] * primes[a[0]] == dp[i - 1]) {
                a[1]++;
                heap.offer(a);
                a = heap.poll();
            }
            dp[i] = dp[a[1]] * primes[a[0]];
            a[1]++;
            heap.offer(a);
        }

        return dp[n];
    }

    public static void main(String[] args) {
        超级丑数 s = new 超级丑数();
        int[] primes = {2, 7, 13, 19};
        System.out.println(s.nthSuperUglyNumber(12, primes));
    }
}
